1. Field of the Invention
The present invention relates to routing connections in a telecommunications network, and, more particularly, to scheduling of traffic connections in input-buffered switches.
2. Description of the Related Art
Input-buffered crossbars are widely used in scaleable, high-speed switches of telecommunications networks since input-buffered crossbars achieve a specified capacity using a lower memory bandwidth than output-buffered switches. Since memory and memory access tends to be the slowest component of a switching system, increasing the scale (or size) of a switch requires reducing memory speed requirements. A number of methods for maximizing the performance of input-buffered architectures have been proposed in the prior art, and an input-buffered switch with virtual output queuing may achieve 100% throughput under arbitrary traffic patterns. Methods are also known in the prior art for input-buffered switch emulation of the quality-of-service behavior of output-buffered-switches for a general class of scheduling disciplines. However, these methods require complex arbitration schemes that execute at every switch scheduling instant (i.e., at the time scale of packet-transmission times).
One class of traffic that requires scheduling is jitter-constrained traffic where the bandwidth requirements of the traffic are known a priori. This scheduling is primarily motivated by the needs of an EF traffic class in a diff-serv framework, and the requirements of bandwidth-guaranteed, low-jitter traffic in MPLS networks. In diff-serv networks, each router is configured to achieve certain per-hop behavior (i.e., behavior through the path between switches). For the EF traffic class, bandwidth is provisioned between the input and output interfaces of a router. Considering the switch fabric of the router, this bandwidth provisioning results in the generation of a “rate matrix” whose elements specify the bandwidth need between every input-output port pair of the switch fabric (e.g., rows of the rate matrix correspond to input ports and columns correspond to output ports). Since this bandwidth need is for carrying EF traffic, the switch must satisfy these bandwidth needs while also satisfying additional stringent requirements on the tolerable jitter. The rate matrix of the switch changes relatively slowly and might be on the order of the provisioning time scales for per-hop behavior.
One method of jitter-constrained, bandwidth-guaranteed scheduling makes the input-buffered switch emulate an output-buffered switch with a fair-queuing scheduler. However, this emulation 1) is complex to implement at high speeds, and 2) does not make use of the fact that the rates through the switch change relatively slowly and are re-computed at packet-transmission time scales.
When the rates are known, an alternative method uses a fixed schedule for time-division multiplexing (TDM) of the switch fabric. The TDM schedule is recalculated only when the rate matrix changes, i.e., when the per-hop behavior if re-provisioned. Input ports may generally maintain different queues for each output port (Virtual Output Queuing), and switching is performed using constant-size packets termed “envelopes” or “slots.”
The static TDM method is referred to as the Guaranteed Rate Table (GRT) method. The basis of the GRT method is that once a rate matrix is provided, the rate matrix is decomposed into schedule tables. The GRT method ensures that every input port has the opportunity to transmit to every output port with a frequency sufficient to guarantee bandwidth needs. These transmission opportunities must be distributed appropriately to satisfy jitter constraints. A reasonable switch design combines the GRT scheme with a throughput-maximizing, matching scheduler that schedules best-effort traffic to utilize the slots not used by the GRT scheme.
A disadvantage of the GRT method is the relatively long time required for calculation of the switch schedule by the method. For a fixed-rate matrix, the schedule is periodic, and consists of a sequence of schedule tables implemented during time slots of the period. Each schedule table represents an interconnection between the input ports and the output ports for a given time slot with the constraint that each input port is connected to at most one output port and each output port is connected to at most one input port. A schedule table for an n×n switch may be represented as an n×n matrix containing zeros and ones such that each row sum and column sum of the matrix is at most one. A “1” in the schedule table position defined by row i and column j of the schedule table's n×n matrix implies that input port i is connected to output port j in this time slot. If each row sum and column sum is exactly one, then each input port is matched to exactly one output port and vice versa. This matrix is termed a permutation matrix. A matrix whose row sums and column sums are at most one without it being a permutation matrix is termed a partial permutation matrix. Therefore, a schedule table may be represented as a permutation matrix or a partial permutation matrix. If the schedule table is a partial permutation matrix, then the input ports and output ports that are not matched may be used to schedule best-effort traffic.
The collection of schedule tables that represent the rate matrix determine the time scale for bandwidth guarantees and the jitter performance that may be achieved by the switch for a given switch capacity. The total amount of bandwidth needed to support all the schedule tables is termed the bandwidth requirement of the switch schedule. In order for a switch schedule to be feasible, the bandwidth requirement of the switch schedule should be less than the switch bandwidth.
In addition, for good bandwidth and jitter performance, there are two additional desirable properties for the scheduling algorithm implementing the switch schedule. First, the execution time of the scheduling method should not be too large since the algorithm may need to run on a switch control processor and not on a high-end computer. Also, even though the rate matrix does not change at packet-switching time scales, it is desirable to have the option of changing the rate matrix at connection-arrival time scales (as for instance in MPLS networks). Second, the number of schedule tables should be relatively small since the tables may need to be stored in a switch schedule arbitrator close to the switch fabric and the memory taken up for table storage should be relatively small.
Prior art scheduling methods for calculating schedule tables are generally based on Birkhoff Von-Neumann (BV) decomposition. BV decomposition employs a BV algorithm that minimizes the bandwidth requirement for the switch schedule while providing provisioned bandwidth guarantees. The BV algorithm does not take into account jitter performance, and a straightforward implementation of the BV algorithm may lead to extremely high jitter that does not meet the requirements of EF class service. The time complexity (related to the execution time) of the BV algorithm is on the order of n4.5 (represented mathematically as O(n4.5)), and the number of schedule tables is O(n2). These time and space requirements make the algorithm impractical for a high-speed switch implementation.
Recalling that each schedule table may be defined as a permutation matrix or a partial permutation matrix, the basis of the BV decomposition is that any doubly stochastic matrix can be written as a convex combination of permutation matrices. Therefore, the BV decomposition of the rate matrix R generates a set of permutation matrices (schedule tables) Yk for k=1,2, . . . , K from the relation as given in equation (1):
                              R          =                                    ∑                              k                =                1                            K                        ⁢                                                  ⁢                                          α                k                            ⁢                              Y                k                                                    ,                            (        1        )            where each αk is a constant, and equation (2) gives the relation for the ith row and jth column rate entry rij of the rate matrix:
                              r                      i            ⁢                                                  ⁢            j                          =                              ∑                          k              =              1                        K                    ⁢                                          ⁢                                    α              k                        ⁢                                          Y                ij                k                            .                                                          (        2        )            
The bandwidth requirement BR of the schedule tables (i.e., the BR of the switch schedule) generated by the BV decomposition is given by equation (3):
                              BR          =                                                    ∑                                  k                  =                  1                                K                            ⁢                                                          ⁢                              α                k                                      =            M                          ,                            (        3        )            where M is the row and column sum of the rate matrix. Thus, the BV decomposition minimizes the bandwidth requirement.
The permutation (switching) matrices may be scheduled across the switch using a Weighted Round Robin (WRR) scheduling method. A BV decomposition may be illustrated with the following (4×4) rate matrix R in equation (4):
                    R        =                  [                                                    0.38                                            0                                            0.22                                            0.40                                                                    0.11                                            0.24                                            0.60                                            0.05                                                                    0                                            0.53                                            0.14                                            0.33                                                                    0.51                                            0.23                                            0.04                                            0.22                                              ]                                    (        4        )            All the row and column sums of the rate matrix R are one (i.e., the rate matrix is doubly stochastic).
The BV decomposition of the rate matrix of equation (4) is shown below in equation (5):
                                                        R              =                            ⁢                                                0.14                  ⁡                                      [                                                                                            1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                      ]                                                  +                                  0.23                  ⁡                                      [                                                                                            1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                      ]                                                  +                                  0.10                  ⁡                                      [                                                                                            0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                      ]                                                  +                                                                                                      ⁢                                                0.01                  ⁡                                      [                                                                                            1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                      ]                                                  +                                  0.36                  ⁡                                      [                                                                                            0                                                                          0                                                                          0                                                                          1                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                      ]                                                  +                                  0.04                  ⁡                                      [                                                                                            0                                                                          0                                                                          0                                                                          1                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          1                                                                          0                                                                                      ]                                                  +                                                                                                      ⁢                                                0.07                  ⁡                                      [                                                                                            0                                                                          0                                                                          1                                                                          0                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                      ]                                                  +                                  0.05                  ⁡                                      [                                                                                            0                                                                          0                                                                          1                                                                          0                                                                                                                      0                                                                          0                                                                          0                                                                          1                                                                                                                      0                                                                          1                                                                          0                                                                          0                                                                                                                      1                                                                          0                                                                          0                                                                          0                                                                                      ]                                                                                                          (        5        )            
The BV decomposition shown in equation (5) has 8 schedule tables, and this BV decomposition of the rate matrix in equation (4) is not unique. In the BV decomposition of the rate matrix R, a given entry rij is divided and spread (“striped”) across several permutation matrices. Therefore, independent of the type of algorithm used to schedule the permutation matrices, there is no control on when individual entries in the rate matrix will be scheduled. It is possible to derive bounds on the jitter, but it is not possible to ensure that the jitter is low. The bounds on the jitter for the traffic between input port i and output port j depend on the number of matrices in the decomposition that rij is striped across and also on the number of matrices in the decomposition. Since both these factors increase with the number of ports in the switch, the jitter problem becomes severe when the number of ports is large. The BV decomposition, therefore, results in poor jitter performance especially when there is a large number of ports in the switch.